home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 22
/
Cream of the Crop 22.iso
/
program
/
ctlib100.zip
/
INSTALL.LZH
/
CTBITREE.INT
< prev
next >
Wrap
Text File
|
1996-10-12
|
6KB
|
169 lines
{**************************************************************************}
{* BitSoft Development, L.L.C. *}
{* Copyright (C) 1995, 1996 BitSoft Development, L.L.C. *}
{* All rights reserved. *}
{* Binary trees unit *}
{* Version 1.2.0 *}
{**************************************************************************}
unit ctBiTree;
{$X+,B-}
interface
uses Objects,
Containr, ctTrees, ctTypes;
type
TraverseOrders = (PreOrder, InOrder, PostOrder);
type
PBinaryNode = ^TBinaryNode;
TBinaryNode = object(TNode)
Left : PBinaryNode;
Right : PBinaryNode;
constructor Init;
constructor Load (var S : TStream);
function Degree : Byte; virtual;
function Height : Word; virtual;
function Leaf : Boolean; virtual;
procedure Store (var S : TStream);
end; { TBinaryNode }
type
PBinaryTree = ^TBinaryTree;
TBinaryTree = object(TTree)
Root : Pointer;
constructor Init;
constructor Load(var S: TStream);
destructor Done; virtual;
function Degree : Word; virtual;
function Delete (Item : Pointer) : Boolean; virtual;
function DeleteAll : Boolean; virtual;
function Find (Key : Pointer; var Hits : LongInt) : Boolean;
virtual;
function FindThat (Key, Test : Pointer; var Hits : LongInt) :
Boolean; virtual;
function First : Pointer; virtual;
function FirstThat (Test : Pointer) : Pointer; virtual;
function ForEach (Action: Pointer): Boolean; virtual;
function ForEachThat(Test, Action : Pointer): Boolean; virtual;
function FreeAll : Boolean; virtual;
function Height : Word; virtual;
function Insert (Item : Pointer) : Boolean; virtual;
function ItemPut (OldItem, NewItem : Pointer) : Boolean; virtual;
function ItemReplace (OldItem, NewItem : Pointer) : Boolean; virtual;
function KeyFirst (Key : Pointer) : Pointer; virtual;
function KeyLast (Key : Pointer) : Pointer; virtual;
function KeyOf(Item : Pointer) : Pointer; virtual;
function Last : Pointer; virtual;
function LastThat(Test : Pointer) : Pointer; virtual;
function Level (Item : Pointer) : Integer; virtual;
function Next (Item : Pointer) : Pointer; virtual;
function NextThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
function Prev (Item : Pointer) : Pointer; virtual;
function PrevThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
procedure Store (var S: TStream);
function Traverse(Action : Pointer; Order : TraverseOrders) : Boolean;
virtual;
function TraverseThat(Test, Action : Pointer; Order : TraverseOrders)
: Boolean; virtual;
private
LastHigh : PBinaryNode;
LastLow : PBinaryNode;
function LocateItem(Item : Pointer) : Boolean;
end; { TBinaryTree }
type
BalanceFactor = (LH, EH, RH);
type
PAVLNode = ^TAVLNode;
TAVLNode = Object(TBinaryNode)
Balance : BalanceFactor;
constructor Init;
constructor Load (var S : TStream);
procedure Store(var S: TStream);
end; { TAVLNode }
type
PAVLTree = ^TAVLTree;
TAVLTree = object(TBinaryTree)
function Insert(Item : Pointer) : Boolean; virtual;
function Delete(Item : Pointer) : Boolean; virtual;
private
procedure BalanceLeft (var Node : PAVLNode);
procedure BalanceRight (var Node : PAVLNode);
procedure RotateLeft (var Node : PAVLNode);
procedure RotateRight (var Node : PAVLNode);
end; { TAVLTree }
type
PStringBinaryNode = ^TStringBinaryNode;
TStringBinaryNode = object(TBinaryNode)
{$ifdef Windows}
Text : PChar;
{$else}
Text : PString;
{$endif WIndows}
{$ifdef Windows}
constructor Init (AString : PChar);
{$else}
constructor Init (AString : String);
{$endif Windows}
constructor Load (var S : TStream);
destructor Done; virtual;
function KeyOf : Pointer; virtual;
procedure Store (var S : TStream);
end; { TStringBinaryNode }
type
PStringAVLNode = ^TStringAVLNode;
TStringAVLNode = object(TAVLNode)
{$ifdef Windows}
Text : PChar;
{$else}
Text : PString;
{$endif WIndows}
{$ifdef Windows}
constructor Init (AString : PChar);
{$else}
constructor Init (AString : String);
{$endif Windows}
constructor Load (var S : TStream);
destructor Done; virtual;
function KeyOf : Pointer; virtual;
procedure Store (var S : TStream);
end; { TStringAVLNode }
procedure RegisterBinaryTrees;
const
RBinaryTree : TStreamRec = (
ObjType : idBinaryTree;
VmtLink : Ofs(TypeOf(TBinaryTree)^);
Load : @TBinaryTree.Load;
Store : @TBinaryTree.Store);
RAVLTree : TStreamRec = (
ObjType : idAVLTree;
VmtLink : Ofs(TypeOf(TAVLTree)^);
Load : @TAVLTree.Load;
Store : @TAVLTree.Store);
RStringBinaryNode : TStreamRec = (
ObjType : idStringBinaryNode;
VmtLink : Ofs(TypeOf(TStringBinaryNode)^);
Load : @TStringBinaryNode.Load;
Store : @TStringBinaryNode.Store);
RStringAVLNode : TStreamRec = (
ObjType : idStringAVLNode;
VmtLink : Ofs(TypeOf(TStringAVLNode)^);
Load : @TStringAVLNode.Load;
Store : @TStringAVLNode.Store);
implementation
end.